package tree.completelyTree;

import pojo.TreeNode;

/**
 * 功能描述:完全二叉树utils : 树中的节点一定是从左至右依次变满的
 *      1. 满二叉树  左树满，右树满 左树高度=右树高度
 *      2. 完全二叉树
 *      2.1 左树不满，右树满 左树高度=右树高度+1
 *      2.1 左树满，右树满 左树高度=右树高度+1
 *      2.1 左树满，右树不满 左树高度=右树高度+1
 * 2024/06/09
 *
 * @author ZhangYi
 */
public class CompletelyTreeUtils {


    /**
     * 功能描述:信息,要搜集的树的节点信息
     * 2024/06/09
     *
     * @author ZhangYi
     */
    public static class Info{
        /**
         * 是满二叉树
         */
        private boolean isFull;
        /**
         * 是完全二叉树
         */
        private boolean isCBT;
        /**
         * 高度
         */
        private int height;

        public Info(boolean isFull,
                    boolean isCBT,
                    int height) {
            this.isFull = isFull;
            this.isCBT = isCBT;
            this.height = height;
        }
    }


    public boolean isCompletelyTree(TreeNode root){
        if (root == null){
            return true;
        }

        return process(root).isCBT;
    }

    private Info process(TreeNode root) {
        if (root == null){
            return new Info(true,true,0);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        // 是满二叉树
        boolean isFull =leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        // 树的高度
        int height = Math.max(leftInfo.height,rightInfo.height)+1;
        boolean isCBT =false;
        if (isFull){
            return new Info(isFull,true,height);
        }else {
            if (leftInfo.isCBT && rightInfo.isCBT){
                if (leftInfo.height == rightInfo.height+1 || leftInfo.height == rightInfo.height){
                    isCBT = true;
                }else if (leftInfo.height == rightInfo.height){
                    isCBT = true;
                }
            }
        }

        return new Info(isFull,isCBT,height);
    }

    public static void main(String[] args) {
        TreeNode root = generateBalanceSearchTree();
        System.out.println(new CompletelyTreeUtils().isCompletelyTree(root));
    }

    private static TreeNode generateBalanceSearchTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.left.right = new TreeNode(11,
                                          "4");


        treeNode.right = new TreeNode(34,
                                      "3");
        return treeNode;
    }

}
